/**
 * Description:
 * Date: 2024-07-20
 * Time: 20:18
 */
public class Main {
    int[] prev; //根节点
    //找 u 的根节点 (不含路径压缩 )
    public int root(int u) {
        if(prev[u] == u) return u;
        return root(prev[u]);
    }

    //合并操作:把 u 的根节点指向 v 的根节点 ( 或者反过来也 ok )
    public void merge(int u,int v) {
        prev[root(u)] = root(v); //u 的根节点指向 v 的
    }

    //查询操作:查询某两个节点的根节点是否相同
    public boolean acquire(int u,int v) { return root(u) == root(v);}

    //找 u 的根节点 (含路径压缩 ),每个节点在它们那一层递归返回的时候,会修改指向,直接指向根节点
    public int root1(int u) {
        return prev[u] = prev[u] == u ? u : root1(prev[u]);
    }
}
